/*
 * @Description: 
 * @Autor: yanwang
 * @Date: 2021-11-05 12:01:02
 * @LastEditors: yanwang
 * @LastEditTime: 2021-11-09 15:26:34
 */

class Node {
  // base: 所有可能出现的字符
  constructor(base = 26) {
    this.flag = false;
    // 存储子节点的地址
    this.next = new Array(base).fill(null);
  }
}

class Trie {
  constructor() {
    this.BASE = 26;  // 假设字典树中只有26个小写英文字母
    this.root = new Node();
  }

  // 插入字符串，返回此字符串是否第一次插入
  insert(word) {
    let p = this.root; // 从根节点开始
    for (let i = 0; i < word.length; i++) {
      const x = word[i];
      const ind = x.charCodeAt() - 'a'.charCodeAt(); // 将字母转换为下标
      
      // 如果子节点中不存在此字母节点，则创建节点。
      if(p.next[ind] === null) p.next[ind] = new Node();
      // 如果已经存在此字母的节点，直接向下移动
      p = p.next[ind];
    }

    if(p.flag) return false; // 非首次插入
    // 字符串插入完毕，最后一个节点改为红色
    p.flag = true;

    return true;
  }
  
  // 返回是否搜索到
  search(word) {
    let p = this.root;
    for (let i = 0; i < word.length; i++) {
      const x = word[i];
      const ind = x.charCodeAt() - 'a'.charCodeAt();
      // 向下查找一步
      p = p.next[ind];
      if(p === null) return false;
    }
    // 可以找到包含word的词，判断是否独立成词。
    return p.flag;
  }

  // 输出所有字符串， 字典树排序后输出
  output() {
    let ret = [];
    this.__output(this.root, '', ret);
    return ret;
  }
  // root: 根节点， s: 前缀 ret：结果数组
  __output(root, s, ret) {
    if(root === null) return;
    if(root.flag) ret.push(s);

    // 遍历所有子节点
    for(let i = 0; i < this.BASE; i++) {
      this.__output(root.next[i], s + String.fromCharCode('a'.charCodeAt() + i), ret);
    }
  }
  
  clearTrie(root) {
    if(root === null) return;
    for (let i = 0; i < this.BASE; i++) clearTrie(root.next[i]);
    root = null;
    return;
  }
}

function test() {
  let trie = new Trie();
  let res;
  res = trie.insert('hello');
  console.log(res);
  res = trie.insert('world');
  console.log(res);
  res = trie.insert('world');
  console.log(res);
  res = trie.search('hello');
  console.log(res);
  res = trie.search('hell');
  console.log(res);
  res = trie.search('world');
  console.log(res);
  let ret = trie.output();
  console.log(ret);
}
test();